def partition(list, left, right, pivot):
    # 将轴值交换至序列的末尾位置（这里选择right位置作为轴值位置）
    list[pivot], list[right] = list[right], list[pivot]
    # 初始化一个游标 i 指向left位置
    i = left
    for j in range(left, right):
        # 如果当前元素小于或等于轴值，则将其与游标 i 指向的元素交换
        if list[j] <= list[right]:
            list[i], list[j] = list[j], list[i]
            i += 1
            # 将轴值元素与 i 指向的元素交换，此时 i 左边的元素都小于等于轴值，i 右边的元素都大于轴值
    list[i], list[right] = list[right], list[i]
    return i


def quickSort(list, left, right):
    # 递归区间只有1个关键码时，无需排序
    if left >= right:
        return
        # 选择最右边的元素作为轴值
    pivot = right
    # 划分操作
    pivotpos = partition(list, left, right, pivot)
    # 递归对左边序列排序
    quickSort(list, left, pivotpos - 1)
    # 递归对右边序列进行排序
    quickSort(list, pivotpos + 1, right)


